import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class mergesort {
    public static void merge_sort(int[] a,int left,int right){
        if(left==right)
            return;
        else if (left<right) {
            int mid=(left+right)/2;
            merge_sort(a,left,mid);
            merge_sort(a,mid+1,right);
            merge(a,left,right);
        }
    }
    public static void merge(int[] a, int left, int right){
        int mid=(left+right)/2;
        int k=mid+1;
        int m=right-left+1;
        int[] b=new int[m];
        int i=0;
        int left0=left;
        while((left<=mid)&&(k<=right)){
            if(a[left]<a[k])
                b[i++]=a[left++];
            else
                b[i++]=a[k++];
        }
        if(left>mid)
            for(;k<=right;k++)
            b[i++]=a[k];
        if(k>right)
            for(;left<=mid;left++)
            b[i++]=a[left];
        for (int j = 0; j < m; j++) {
            a[left0++]=b[j];
        }
    }

    public static void main(String[] args) {
        Random random=new Random();
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=random.nextInt(100);
        }
        merge_sort(a,0, a.length-1);
        System.out.println(Arrays.toString(a));
    }
}
